#include <vector>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int _val = 0, TreeNode* _left = nullptr, TreeNode* _right = nullptr)
    {
        val = _val;
        left = _left;
        right = _right;
    }
};


//非递归(迭代)后序遍历
vector<int> backOrder(TreeNode* root)
{
	vector<int> v = {};
	stack<TreeNode*> st;
	TreeNode* cur = root;
	TreeNode* prev = nullptr;
	while (cur || !st.empty())
	{
		while (cur) {
			st.push(cur);
			cur = cur->left;
		}
		TreeNode* tmp = st.top();
		//若取出节点的右子树为空，或右子树已经访问过了，则访问该节点
		if (tmp->right == nullptr || tmp->right == prev) {
			st.pop();
			v.emplace_back(tmp->val);
			prev = tmp;
		}
		else {
			cur = tmp->right;
		}
	}
	return v;
}



//1.输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。注意，路径定义为从树的根结点
//开始往下一直到叶结点所经过的结点形成的一条路径。

void dfs(TreeNode* root, vector<vector<int>>& vv, vector<int>& v, int sum)
{
    if (nullptr == root)
        return;
    sum -= root->val;
    v.emplace_back(root->val);
    if (nullptr == root->left && nullptr == root->right && 0 == sum)
        vv.push_back(v);
    dfs(root->left, vv, v, sum);
    dfs(root->right, vv, v, sum);
    v.pop_back();
}
vector<vector<int>> findPath(TreeNode* root, int sum)
{
    vector<vector<int>> res;
    vector<int> v;
    dfs(root, res, v, sum);
    return res;
}

//2.判断两个二叉树是否是镜像的

bool binaryMirrorJudge(TreeNode* root1, TreeNode* root2)
{
    //两个节点都是空的
    if (nullptr == root1 && nullptr == root2)
        return true;
    //其中一个节点为空
    if (nullptr == root1 || nullptr == root2)
        return false;
    //两个节点都不为空
    if (root->val != root2->val)
        return false;
    //进行递归
    bool res = true;
    res = binaryMirrorJudge(root1->left, root2->right);//遍历顺序是前序遍历（因为要从第一个节点开始一个一个往下比较）
    if (res)//如果左子树中出现不相等的节点值则res就被置为false，不用在判断右子树
        res = binaryMirrorJudge(root1)
        return res;
}

//3.将一个二叉树变为它的镜像二叉树

void becomeMirror(TreeNode* root)
{
    if (nullptr == root)
        return;
    TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    becomeMirror(root->left);
    becomeMirror(root->right);
    return;
}

//4.输入两个二叉树A和B，判断B是否是A的子结构。请注意，空树不是任何树的子结构。

//首先我们得找到A中与B的第一个节点相同的节点，然后在进行判断
bool judgeBegin(TreeNode* begin, TreeNode* root2)
{
    //判断为空情况
    if (nullptr == root2)
        return true;
    if (nullptr == begin)
        return false;
    //如果节点都不为空，那就进行节点值比较
    if (begin->val != root2->val)
        return false;
    bool res = true;
    /*if (res)
        res = judgeBegin(begin->left, root2->left);
    if (res)
        res = judgeBegin(begin->right, root2->right);
    return res;*/
    return judgeBegin(begin->left, root2->left) && judgeBegin(begin->right, root2->right);
}
bool judgeChildStructure(TreeNode* root1, TreeNode* root2)
{
    if (nullptr == root1 || nullptr == root2)
        return false;
    bool res = false;
    //此时在A树中找到了以B树第一个节点相同的节点，然后开始比较
    if (root1->val == root2->val)
        res = judgeBegin(root1, root2);
    if (false == res)
        res = judgeBegin(root1->left, root2);
    if (false == res)
        res = judgeBegin(root1->right, root2);
    return res;
}